We are interested in finding anO(ε)-stationary point of the functionΦ( ) = maxy Yf( ,y). Thisminimax optimization formulation includes manymachine learning applications such as regularized empirical risk minimization [42, 53], AUC maximization [40, 49], robust optimization [14, 47], adversarial training [16, 17, 41] and reinforcement learning [13, 44].

However, all known theoretical rates are worse than the rate of gradient descent, which synchronizes after every gradient step.

We develop a new primitive for stochastic optimization: a low-bias, low-cost estimator of the minimizerx? of any Lipschitz strongly-convex function.